
/*将算术表达式转化为后缀表达式*/
function RPNtrans(str) {
    let i = 0, ch = '';
    let opts = [], top = -1;
    let rpn = [], t = -1;
    while (i < str.length) {
        ch = str[i];
        switch (ch) {
            case '(':
                top++;
                opts[top] = ch;
                break;
            case ')':
                while (opts[top] != '(') {
                    t++;
                    rpn[t] = opts[top];
                    top--;
                }
                top--;
                break;
            case '+':
            case '-':
                while (top >= 0 && opts[top] != '(') {
                    t++;
                    rpn[t] = opts[top];
                    top--;
                }
                top++;
                opts[top] = ch;
                break;
            case '*':
            case '/':
                while (opts[top] == '*' || opts[top] == '/') {
                    t++;
                    rpn[t] = opts[top];
                    top--;
                }
                top++;
                opts[top] = ch;
                break;
            case ' ':
                break;
            default:
                if (ch >= '0' && ch <= '9') {
                    let num = '';
                    while (ch >= '0' && ch <= '9') {
                        num += ch;
                        i++;
                        ch = str[i];
                    }
                    t++;
                    rpn[t] = num;
                    i--;
                }
                break;
        }
        i++;
    }
    while (top >= 0) {
        t++;
        rpn[t] = opts[top];
        top--;
    }
    console.log("RPN: ", rpn.toString());
    return rpn;
}

/*计算后缀表达式的值*/
function RPNvalue(rpn) {
    let i = 0, ch = '';
    let opts = [], top = -1;
    while (i < rpn.length) {
        ch = rpn[i];
        switch (ch) {
            case '+':
                opts[top - 1] = opts[top - 1] + opts[top];
                top--;
                break;
            case '-':
                opts[top - 1] = opts[top - 1] - opts[top];
                top--;
                break;
            case '*':
                opts[top - 1] = opts[top - 1] * opts[top];
                top--;
                break;
            case '/':
                if (opts[top] != 0) {
                    opts[top - 1] = opts[top - 1] / opts[top];
                }
                else {
                    return NaN;
                }
                top--;
                break;
            default:
                if (ch[0] >= '0' && ch[0] <= '9') {
                    let num = parseInt(ch)
                    top++;
                    opts[top] = num;
                }
                break;
        }
        i++;
    }
    return opts[top];
}

let str = "(21 + 31 * 4 * 3) * 3 * 3 / (5 - 2) * 2 + (51 - 31 + 2) * 2 / 2 + 13 * 2";
console.log(str);
console.log("eval: ", eval(str));
console.log("RPN:  ", RPNvalue(RPNtrans(str)));